package 笔试题;

import java.util.Map;

public class lk_115 {
    public static void main(String[] args) {
        System.out.println(numDistinct("ddd", "dd"));
//        numDistinct("rabbbit", "rabbit");
    }
    public static int numDistinct(String s, String t) {
        int[][] k = new int[2][s.length()];
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int b = 0;
        for (int i = 0; i < ts.length; i++) {
            for (int j = 0; j < ss.length; j++) {
                if(ts[i]==ss[j]){
                    b = 1;
                }
                if(i == 0){
                    if(j == 0){
                        k[i&1][j] = b;
                    }else{
                        k[i&1][j] = k[i&1][j-1]+b;
                    }
                }else{
                    if(j == 0){
                        k[i&1][j] = 0;
                    }else{
                        if(b == 1){
                            k[i&1][j] = k[i&1][j-1] + k[(i-1)&1][j-1];
                        }else{
                            k[i&1][j] = k[i&1][j-1];
                        }
                    }
                }

                b = 0;
            }
            for (int j = 0; j < ss.length; j++) {
                System.out.print(k[i&1][j] + "\t");
            }
            System.out.println();
        }
        return k[(ts.length-1)&1][s.length()-1];

    }
    public static int numDistinct2(String s, String t) {
        char[] ts = t.toCharArray();
        char[] ss = s.toCharArray();


        return db(ss,0,ts,0);

    }
    public static int db(char[] ss,int ssNum,char[] ts,int tsNum){
        int re = 0;
        if(ss.length == ssNum){
            return re;
        }
        for (int i=ssNum;i<ss.length;i++){
            if(ss[i] == ts[tsNum]){
                if(ts.length-1 == tsNum){
                    re++;
                }else{
                    re += db(ss,i+1,ts,tsNum+1);
                }
            }
        }
        return  re;
    }

}
